package com.he.algorithm.order;

import java.util.Arrays;

/**
 * @description: 快速排序  双指针
 * @Author: HCL
 * @Date: 2024/9/3 9:57
 */
public class QuickSort {

    //推荐使用
    /**
    * 注意：
     * 当基准值使用索引最小的树时，先判断右边(while)，再判断左边
     * 当基准值使用索引最大的树时，先判断左边(while)，再判断右边
     *
    */
    public static void sort(int[] nums, int left, int right) {
        if (nums == null || nums.length == 0 || left > right) {
            return;
        }
        //使用中间索引，其他代码保持不变
        {
//            // 计算中间索引
//            int mid = left + (right - left) / 2;
//            // 将中间元素与最左边的元素交换
//            int tempLeft = nums[left];
//            nums[left] = nums[mid];
//            nums[mid] = tempLeft;
        }
        int pivot = nums[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        //此时i==j,交换基准值和当前值的位置
        nums[left] = nums[i];
        nums[i] = pivot;

        sort(nums, left, j - 1);
        sort(nums, i + 1, right);
    }

    public static void sort2(int[] nums, int left, int right) {
        if (nums == null || left >= right){
            return;
        }
        int pivotIndex = partition(nums, left, right);
        sort2(nums, left, pivotIndex - 1);
        sort2(nums, left + 1, pivotIndex);
    }

    public static int partition(int[] nums, int left, int right) {
        if (nums == null || left > right){
            return left;
        }
        int pivot = nums[left];
        int i = left;
        int j = right;
        while (i != j) {
            while (i < j && nums[j] >= pivot) {
                j--;
            }
            while (i < j && nums[i] <= pivot) {
                i++;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        nums[left] = nums[i];
        nums[i] = pivot;

        //返回基准元素的索引
        return i;
    }


    public static void main(String[] args) {
        int[] nums = {7, 1, 3, 9, 5, 2, 6};
        sort(nums, 0, nums.length - 1);
//        sort2(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
